package com.zhang.sort;

/**
 * @author ZhangJiXin
 * @Description 计数排序简单实现版
 * @date 2021/4/25 10:14
 */
public class CountingSort extends Sort<Integer>{
    /**
     *  查找数组最大数字 来创建最大数字长度的数组
     *  用新数组的索引代表 元素 然后记录出现的次数
     *  最后遍历新创建的数组 给原数组进行排序
     *  这种实现方法缺点：
     *  ①空间复杂度非常大
     *  ②不是稳定排序
     *  ③不能给 负数进行排序
     * @Author ZhangJiXin
     * @Date 2021/4/26 8:37
     * @return: void
     */
    @Override
    protected void sort() {
        //找到最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]){
                max = array[i];
            }
        }
        int[] list = new int[max + 1];
        //记录元素出现的次数
        for (int i = 0; i < array.length; i++) {
            list[array[i]]++;
        }
        //进行排序
        int begin = 0;
        for (int i = 0; i < list.length; i++) {
            while (list[i]-- > 0){
                array[begin++] = i;
            }
        }
    }
}
